{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum Obtained of Any Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumRangeQuery"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有排列中的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个整数数组&nbsp;<code>nums</code>&nbsp;，和一个查询数组&nbsp;<code>requests</code>&nbsp;，其中&nbsp;<code>requests[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>&nbsp;。第&nbsp;<code>i</code>&nbsp;个查询求&nbsp;<code>nums[start<sub>i</sub>] + nums[start<sub>i</sub> + 1] + ... + nums[end<sub>i</sub> - 1] + nums[end<sub>i</sub>]</code>&nbsp;的结果&nbsp;，<code>start<sub>i</sub></code> 和&nbsp;<code>end<sub>i</sub></code>&nbsp;数组索引都是 <strong>从 0 开始</strong> 的。</p>\n",
    "\n",
    "<p>你可以任意排列 <code>nums</code>&nbsp;中的数字，请你返回所有查询结果之和的最大值。</p>\n",
    "\n",
    "<p>由于答案可能会很大，请你将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,4,5], requests = [[1,3],[0,1]]\n",
    "<strong>输出：</strong>19\n",
    "<strong>解释：</strong>一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：\n",
    "requests[0] -&gt; nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8\n",
    "requests[1] -&gt; nums[0] + nums[1] = 2 + 1 = 3\n",
    "总和为：8 + 3 = 11。\n",
    "一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：\n",
    "requests[0] -&gt; nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11\n",
    "requests[1] -&gt; nums[0] + nums[1] = 3 + 5  = 8\n",
    "总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,4,5,6], requests = [[0,1]]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>一个总和最大的排列为 [6,5,4,3,2,1] ，查询和为 [11]。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]\n",
    "<strong>输出：</strong>47\n",
    "<strong>解释：</strong>一个和最大的排列为 [4,10,5,3,2,1] ，查询结果分别为 [19,18,10]。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i]&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= requests.length &lt;=&nbsp;10<sup>5</sup></code></li>\n",
    "\t<li><code>requests[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub>&nbsp;&lt;= end<sub>i</sub>&nbsp;&lt;&nbsp;n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-obtained-of-any-permutation](https://leetcode.cn/problems/maximum-sum-obtained-of-any-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-obtained-of-any-permutation](https://leetcode.cn/problems/maximum-sum-obtained-of-any-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n[[1,3],[0,1]]', '[1,2,3,4,5,6]\\n[[0,1]]', '[1,2,3,4,5,10]\\n[[0,2],[1,3],[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        length = len(nums)\n",
    "        \n",
    "        counts = [0] * length\n",
    "        for start, end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < length:\n",
    "                counts[end + 1] -= 1\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i - 1]\n",
    "\n",
    "        counts.sort()\n",
    "        nums.sort()\n",
    "        \n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        return total % MODULO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        length = len(nums)\n",
    "        \n",
    "        counts = [0] * length\n",
    "        for start, end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < length:\n",
    "                counts[end + 1] -= 1\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i - 1]\n",
    "\n",
    "        counts.sort()\n",
    "        nums.sort()\n",
    "        \n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        return total % MODULO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        mod = int(1e9 + 7)\n",
    "        # 0 - (n-1)\n",
    "        diff = [0] * (n + 1)\n",
    "\n",
    "        for a, b in requests:\n",
    "            diff[a] += 1\n",
    "            diff[b + 1] -= 1\n",
    "        \n",
    "\n",
    "\n",
    "        ls = []\n",
    "\n",
    "        sum_ = 0\n",
    "        for i in range(n):\n",
    "            sum_ += diff[i]\n",
    "\n",
    "            ls.append(sum_)\n",
    "        \n",
    "        ls.sort(key = lambda x:-x)\n",
    "        nums.sort(reverse = True)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            ans += (nums[i] * ls[i]) % mod\n",
    "            ans %= mod\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        a = [0 for _ in range(n+1)]\n",
    "        b = [0 for _ in range(n)]\n",
    "        for r in requests:\n",
    "            a[r[0]] += 1\n",
    "            a[r[1]+1] -= 1\n",
    "        b[0] = a[0]\n",
    "        for i in range(1, n):\n",
    "            b[i] = b[i-1] + a[i]\n",
    "        #print(b)\n",
    "        nums.sort(reverse=True)\n",
    "        b.sort(reverse=True)\n",
    "        return sum([b[i]*nums[i] for i in range(n)])%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "\t\tfrequency = [0 for i in range(len(nums))]\n",
    "\t\tSUM = 0\n",
    "\t\tnums.sort()\n",
    "\t\t#  使用差分数组计算频率\n",
    "\t\tfor sub_list in requests:\n",
    "\t\t\tfrequency[sub_list[0]] += 1\n",
    "\t\t\tif sub_list[1] + 1 < len(nums):\n",
    "\t\t\t\tfrequency[sub_list[1] + 1] -= 1\n",
    "\t\t\t\t\n",
    "\t\tfor index in range(1, len(nums)):\n",
    "\t\t\tfrequency[index] = frequency[index] + frequency[index - 1]\n",
    "\t\tfrequency.sort()\n",
    "\t\t\n",
    "\t\tfor index, temp_fre in enumerate(frequency):\n",
    "\t\t\tSUM += temp_fre * nums[index]\n",
    "\t\treturn SUM % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "\n",
    "        for x, y in requests:\n",
    "            diff[x] += 1\n",
    "            diff[y + 1] -= 1\n",
    "        \n",
    "        cnt = [0] * n\n",
    "        curs = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            curs += diff[i]\n",
    "            cnt[i] = curs\n",
    "        \n",
    "        cnt.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = (ans + cnt[i] * nums[i]) % (10 ** 9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        nums.sort()\n",
    "        nl = len(nums)\n",
    "        res = [0 for i in range(0, nl)]\n",
    "        m = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for start ,end in requests:\n",
    "            res[start] = res[start] + 1\n",
    "            if end + 1 < nl:\n",
    "                res[end + 1] =  res[end + 1] - 1\n",
    "\n",
    "        for i in range(1, nl):\n",
    "            res[i] = res[i] + res[i-1]\n",
    "        res.sort()\n",
    "        # print(res)\n",
    "        # print(nums)\n",
    "        for i in range(0, nl):\n",
    "            m = (m + res[i] * nums[i]) % MOD\n",
    "        return m\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        # 计算差分数组\n",
    "        times = [0] * len(nums)\n",
    "        for left, right in requests:\n",
    "            times[left] += 1\n",
    "            if right + 1 < len(nums):\n",
    "                times[right + 1] -= 1\n",
    "\n",
    "        # 使用差分数组计算频数\n",
    "        for i in range(1, len(times)):\n",
    "            times[i] += times[i - 1]\n",
    "\n",
    "        times.sort(reverse=True)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            ans += nums[i] * times[i]\n",
    "            if times[i] == 0:\n",
    "                break\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        a = [0]*n\n",
    "        for req in requests:\n",
    "            a[req[0]] += 1\n",
    "            if req[1] < n-1:\n",
    "                a[req[1]+1] -= 1\n",
    "        for i in range(1,n):\n",
    "            a[i] += a[i-1]\n",
    "        a.sort()\n",
    "        nums.sort()\n",
    "        return sum((x*y % MOD) for x,y in zip(a,nums)) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        # 显然是差分数组统计次数，然后按照次数排序\n",
    "        n = len(nums)\n",
    "        d = [0 for i in range(n+1)]\n",
    "        for l, r in requests:\n",
    "            d[l] += 1\n",
    "            d[r+1] -= 1\n",
    "        for i in range(1, n):\n",
    "            d[i] += d[i-1]\n",
    "        \n",
    "        nums.sort()\n",
    "        pre = sorted(d[:-1])\n",
    "        return sum(x * y for x, y in zip(pre, nums)) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort(reverse = True)\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 1)\n",
    "        for s, e in requests:\n",
    "            f[s] += 1\n",
    "            f[e + 1] -= 1\n",
    "        arr = list(accumulate(f[:-1]))\n",
    "        arr.sort(reverse = True)\n",
    "        return sum(a * b for a, b in zip(arr, nums)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        a = [0]*n\n",
    "        for req in requests:\n",
    "            a[req[0]] += 1\n",
    "            if req[1] < n-1:\n",
    "                a[req[1]+1] -= 1\n",
    "        for i in range(1,n):\n",
    "            a[i] += a[i-1]\n",
    "        a.sort()\n",
    "        nums.sort()\n",
    "        return sum(x*y for x,y in zip(a,nums)) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        pre = [0] * (n + 1)\n",
    "        for q1, q2 in requests:\n",
    "            pre[q1] += 1\n",
    "            pre[q2 + 1] -= 1\n",
    "        #presum = [0] * (n+2)\n",
    "        for i in range(1,n):\n",
    "            pre[i] += pre[i - 1]\n",
    "        #print(pre)\n",
    "        pre.sort()\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for v, t in sorted(zip(pre[1:n+1], nums)):\n",
    "            ans += v * t\n",
    "            ans %= M\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "\n",
    "        for x, y in requests:\n",
    "            diff[x] += 1\n",
    "            diff[y+1] -= 1\n",
    "        \n",
    "        cnt = [0] * n\n",
    "\n",
    "        cursum = 0\n",
    "        for i in range(n):\n",
    "             cursum += diff[i]\n",
    "             cnt[i] = cursum\n",
    "        \n",
    "        cnt.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = (ans +  cnt[i] * nums[i]) % (10 ** 9 + 7)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        nums.sort()\n",
    "        length = len(nums)\n",
    "        counts = [0 for _ in range(length)]\n",
    "        for request in requests:\n",
    "            counts[request[0]]+=1\n",
    "            if request[1]+1 < length:\n",
    "                counts[request[1]+1]-=1\n",
    "\n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i-1]\n",
    "        counts.sort()\n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        M = 10**9 + 7\n",
    "        return (total)% M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = int(1e9+7)\n",
    "        cnt = [0] * (n+1)\n",
    "        for st, end in requests:\n",
    "            cnt[st] += 1\n",
    "            cnt[end+1] -= 1\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += cnt[i]\n",
    "            cnt[i] = s\n",
    "        cnt.pop()\n",
    "\n",
    "        cnt.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for x, y in zip(cnt, nums):\n",
    "            if y == 0:\n",
    "                break\n",
    "            ans = (ans + x * y) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        freq = [0] * n\n",
    "        for s, e in requests:\n",
    "            freq[s] += 1\n",
    "            if e + 1 < n:\n",
    "                freq[e+1] -= 1\n",
    "        for i in range(1, n):\n",
    "            freq[i] += freq[i-1]\n",
    "        freq.sort(reverse = True)\n",
    "        nums.sort(reverse = True)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for v in freq:\n",
    "            ans += nums[i] * v\n",
    "            i += 1\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        record = [0 for _ in range(n)]\n",
    "        for x, y in requests:\n",
    "            record[x] += 1\n",
    "            if y < n-1:\n",
    "                record[y+1] -= 1\n",
    "        for i in range(1, n):\n",
    "            record[i] += record[i-1]\n",
    "        # print(record)\n",
    "        nums.sort(reverse=True)\n",
    "        temp = sorted(record, reverse=True)\n",
    "        # print(temp, nums)\n",
    "        res = 0\n",
    "        for i in range(len(temp)):\n",
    "            res = (res + nums[i] * temp[i])%1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        d = [0 for i in range(len(nums)+1)]\n",
    "        for s,e in requests:\n",
    "            d[s] += 1\n",
    "            d[e+1] -= 1\n",
    "        pre = 0\n",
    "        for i in range(len(d)):\n",
    "            d[i] += pre\n",
    "            pre = d[i]\n",
    "        d.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res = (res + nums[i]*d[i])%1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        counts = [0]*(len(nums)+1)\n",
    "        for start, end in requests:\n",
    "            for i in range(start,end+1):\n",
    "                counts[i]+=1\n",
    "        counts.sort(reverse = True)\n",
    "        nums.sort(reverse = True)\n",
    "        MOUDLE = 10**9+7\n",
    "        ans = sum (num*count for num,count in zip(counts,nums))\n",
    "        return ans % MOUDLE\n",
    "        \"\"\"\n",
    "        MODULO = 10**9 + 7\n",
    "        length = len(nums)\n",
    "        \n",
    "        counts = [0] * length\n",
    "        for start, end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < length:\n",
    "                counts[end + 1] -= 1\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i - 1]\n",
    "\n",
    "        counts.sort()\n",
    "        nums.sort()\n",
    "        \n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        return total % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = int(1e9+7)\n",
    "        cnt = [0] * n\n",
    "        for st, end in requests:\n",
    "            cnt[st] += 1\n",
    "            if end+1 < n:\n",
    "                cnt[end+1] -= 1\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += cnt[i]\n",
    "            cnt[i] = s\n",
    "        \n",
    "        cnt.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for x, y in zip(cnt, nums):\n",
    "            if y == 0:\n",
    "                break\n",
    "            ans = (ans + x * y) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for s, e in requests:\n",
    "            diff[s] += 1\n",
    "            diff[e + 1] -= 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            diff[i] += diff[i-1]\n",
    "\n",
    "        diff.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        res = 0\n",
    "        for d, n in zip(diff, nums):\n",
    "            if d == 0:\n",
    "                break\n",
    "            else:\n",
    "                res += d * n\n",
    "\n",
    "        return res % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        a = [0]*n\n",
    "        for k,v in requests:\n",
    "            a[k] += 1\n",
    "            if v < n-1:\n",
    "                a[v+1] -= 1\n",
    "        for i in range(1,n):\n",
    "            a[i] += a[i-1]\n",
    "        a.sort()\n",
    "        nums.sort()\n",
    "        return sum(x*y for x,y in zip(a,nums)) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for s, e in requests:\n",
    "            diff[s] += 1\n",
    "            diff[e + 1] -= 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            diff[i] += diff[i-1]\n",
    "\n",
    "        diff.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        # res = 0\n",
    "        # for d, n in zip(diff, nums):\n",
    "        #     if d == 0:\n",
    "        #         break\n",
    "        #     else:\n",
    "        #         res += d * n\n",
    "\n",
    "        res = sum(d * n for d, n in zip(diff, nums))\n",
    "        return res % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        # nums.sort(reverse=True)\n",
    "        # dic = defaultdict(int)\n",
    "        # for x, y in requests:\n",
    "        #     for i in range(x, y+1):\n",
    "        #         dic[i] += 1\n",
    "        # dic1 = sorted(dic.items(),key = lambda x:x[1], reverse=True)\n",
    "        # n = len(dic1)\n",
    "\n",
    "        # i = 0\n",
    "        # res = 0\n",
    "        # while i < n:\n",
    "        #     res += (nums[i] * dic1[i][1])\n",
    "\n",
    "        #     i += 1\n",
    "        # return res % (10 ** 9 + 7)\n",
    "        MODULO = 10**9 + 7\n",
    "        length = len(nums)\n",
    "        \n",
    "        counts = [0] * length\n",
    "        for start, end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < length:\n",
    "                counts[end + 1] -= 1\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i - 1]\n",
    "\n",
    "        counts.sort()\n",
    "\n",
    "        nums.sort()\n",
    "        \n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        return total % MODULO\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        length = len(nums)\n",
    "        \n",
    "        counts = [0] * length\n",
    "        for start, end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < length:\n",
    "                counts[end + 1] -= 1\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i - 1]\n",
    "\n",
    "        counts.sort()\n",
    "        nums.sort()\n",
    "        \n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        return total % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        #requests = sorted(requests, key=lambda x:x[0])\n",
    "        pre_start,pre_end = requests[0]\n",
    "        MODULO = 10**9 + 7\n",
    "        #计算区间每个元素被几个区间穿过\n",
    "        cnts = [0]*len(nums)\n",
    "        for i in range(0, len(requests)):\n",
    "            start,end = requests[i]\n",
    "            cnts[start] += 1\n",
    "            if end+1 < len(nums): #到end结束\n",
    "                cnts[end+1] -= 1\n",
    "        for i in range(1, len(nums)):\n",
    "            cnts[i] += cnts[i-1]\n",
    "        cnts = sorted(cnts)\n",
    "        #print(cnts )\n",
    "        ans = 0\n",
    "        nums = sorted(nums)\n",
    "        for i in range(len(cnts)):\n",
    "            ans += nums[i]*cnts[i]\n",
    "        return ans%MODULO\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        n = len(nums)\n",
    "        arr = [0]*(n+1)\n",
    "        for start, end in requests:\n",
    "            arr[start] += 1\n",
    "            arr[end+1] -= 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            arr[i] = (arr[i] + arr[i-1]) % MOD\n",
    "        \n",
    "        nums.sort()\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(sorted(arr[:n])):\n",
    "            ans = (ans + nums[i]*v) % MOD\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        lst=[0]*(len(nums)+1)\n",
    "        for r in requests:\n",
    "            lst[r[0]]+=1\n",
    "            lst[r[1]+1]-=1\n",
    "        sum_lst=[0]*len(nums)\n",
    "        curr=0\n",
    "        for i in range(len(lst)-1):\n",
    "            curr+=lst[i]\n",
    "            sum_lst[i]=curr\n",
    "        res=0\n",
    "        sum_lst=sorted(sum_lst,reverse=True)\n",
    "        nums=sorted(nums,reverse=True)\n",
    "        i=0\n",
    "        while i<len(sum_lst) and sum_lst[i]>0:\n",
    "            res+=sum_lst[i]*nums[i]\n",
    "            i+=1\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "                n = len(nums)\n",
    "                diff = [0] * (n + 1)\n",
    "                \n",
    "                for l,r in requests:\n",
    "                    diff[l] += 1\n",
    "                    diff[r+1] -= 1\n",
    "                for i in range(1,n):\n",
    "                    diff[i] += diff[i-1]\n",
    "                diff.sort()\n",
    "                nums.sort()\n",
    "                \n",
    "                ans = 0; j = n \n",
    "                for i in range(n-1,-1,-1):\n",
    "                    if not diff[j]:break\n",
    "                    ans += nums[i] * diff[j]\n",
    "                    j -= 1\n",
    "                return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "贪心\n",
    "每次查询的范围都是一个子数组，因此可以根据查询数组 requests 计算得到数组 nums 的\n",
    "每个下标位置被查询的次数。题目要求返回所有查询结果之和的最大值，当查询结果之和最\n",
    "大时，应满足数组 nums 中的越大的数字被查询的次数越多，因此可以使用贪心算法求解。\n",
    "'''\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        length = len(nums)\n",
    "        \n",
    "        counts = [0] * length\n",
    "        for start, end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < length:\n",
    "                counts[end + 1] -= 1\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i - 1]\n",
    "\n",
    "        counts.sort()\n",
    "        nums.sort()\n",
    "        \n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        return total % MODULO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n=len(nums)\n",
    "        arr=[0]*(n+1)\n",
    "        for l,r in requests:\n",
    "            arr[l]+=1\n",
    "            arr[r+1]-=1\n",
    "        for i in range(1,n):\n",
    "            arr[i]+=arr[i-1]\n",
    "        arr.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(map((lambda x,y:x*y),arr,nums))%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\r\n",
    "        diff = [0] * (len(nums) + 1)\r\n",
    "        for [l, r] in requests:\r\n",
    "            diff[l] += 1\r\n",
    "            diff[r + 1] -= 1\r\n",
    "        for i in range(1,len(diff)):\r\n",
    "            diff[i] += diff[i - 1]\r\n",
    "        diff.sort()\r\n",
    "        nums.sort()\r\n",
    "        res = 0\r\n",
    "        p = len(diff) - 1\r\n",
    "        for i in range(len(nums) - 1, -1, -1):\r\n",
    "            res += nums[i] * diff[p]\r\n",
    "            p -= 1\r\n",
    "        return res % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = int(1e9+7)\n",
    "        cnt = [0] * (n+1)\n",
    "        for st, end in requests:\n",
    "            cnt[st] += 1\n",
    "            cnt[end+1] -= 1\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += cnt[i]\n",
    "            cnt[i] = s\n",
    "        cnt.pop()\n",
    "\n",
    "        cnt.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for x, y in zip(cnt, nums):\n",
    "            if y == 0:\n",
    "                break\n",
    "            ans += x * y\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # ^ 差分 & 贪心\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for s, e in requests:\n",
    "            diff[s] += 1\n",
    "            diff[e + 1] -= 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            diff[i] += diff[i-1]\n",
    "\n",
    "        diff.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        res = 0\n",
    "        for d, n in zip(diff, nums):\n",
    "            if d == 0:\n",
    "                break\n",
    "            else:\n",
    "                res += d * n\n",
    "\n",
    "        return res % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        length = len(nums)\n",
    "        \n",
    "        counts = [0] * length\n",
    "        for start, end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < length:\n",
    "                counts[end + 1] -= 1\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            counts[i] += counts[i - 1]\n",
    "\n",
    "        counts.sort()\n",
    "        nums.sort()\n",
    "        \n",
    "        total = sum(num * count for num, count in zip(nums, counts))\n",
    "        return total % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        MODULO = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "\n",
    "        counts = [0] * n\n",
    "        for start,end in requests:\n",
    "            counts[start] += 1\n",
    "            if end + 1 < n :\n",
    "                counts[end + 1] -= 1\n",
    "        for i in range(1,n):\n",
    "            counts[i] += counts[i-1]\n",
    "        \n",
    "        counts.sort()\n",
    "        nums.sort()\n",
    "\n",
    "        total = sum(num * count for num,count in zip(nums,counts))\n",
    "        return total % MODULO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(nums)\n",
    "        diff = [0]*(n+1)\n",
    "        for st,ed in requests:\n",
    "            diff[st] += 1\n",
    "            diff[ed+1] -= 1\n",
    "        frequecy = list(accumulate(diff))\n",
    "        frequecy.sort(reverse=True)\n",
    "        nums.sort(reverse = True)\n",
    "        ans = sum(num*fr for num,fr in zip(nums,frequecy))%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        n = len(nums) \n",
    "        diff = [0] * n\n",
    "        for x, y in requests:\n",
    "            diff[x] += 1\n",
    "            if y + 1 < n:\n",
    "                diff[y + 1] -= 1\n",
    "            # print(f'{diff,list(accumulate(diff))}')\n",
    "        a = list(accumulate(diff))\n",
    "        a.sort(key=lambda x: -x)\n",
    "        nums.sort(key=lambda x: -x)\n",
    "        ans = 0\n",
    "        for x, y in zip(a, nums):\n",
    "            ans = (ans + x * y) % (10**9 +7)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        diff = [0]*n\n",
    "        for i, j in requests:\n",
    "            diff[i] += 1\n",
    "            if j+1 < n:\n",
    "                diff[j+1] -= 1\n",
    "        diff = list(accumulate(diff))\n",
    "        diff.sort(reverse=True)\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(nums[i]*diff[i] for i in range(n)) % mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
